Search Results

Documents authored by Spieksma, Frits C. R.

Found 2 Possible Name Variants:

Spieksma, Frits C. R.

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.45
Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm

Authors: Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The problem is to partition the given 4k vectors into k quads with minimum total cost. We analyze a straightforward matching-based algorithm and prove that this algorithm is a 3/2-approximation algorithm for this problem. We further analyze the performance of this algorithm on a hierarchy of special cases of the problem and prove that, in one particular case, the algorithm is a 5/4-approximation algorithm. Our analysis is tight in all cases except one.
Cite as

Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma. Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 45:1-45:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ficker_et_al:LIPIcs.ISAAC.2018.45,
  author =	{Ficker, Annette M. C. and Erlebach, Thomas and Mihal\'{a}k, Mat\'{u}s and Spieksma, Frits C. R.},
  title =	{{Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{45:1--45:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.45},
  URN =		{urn:nbn:de:0030-drops-99933},
  doi =		{10.4230/LIPIcs.ISAAC.2018.45},
  annote =	{Keywords: approximation algorithm, matching, clustering problem}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.27
The Lockmaster's problem

Authors: Sofie Coene and Frits C. R. Spieksma

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Inland waterways form a natural network that is an existing, congestion free infrastructure with capacity for more traffic. The European commission promotes the transportation of goods by ship as it is a reliable, efficient and environmental friendly way of transport. A bottleneck for transportation over water are the locks that manage the water level. The lockmaster's problem concerns the optimal strategy for operating such a lock. In the lockmaster's problem we are given a lock, a set of ships coming from downstream that want to go upstream, and another set of ships coming from upstream that want to go downstream. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper a dynamic programming algorithm (DP) is proposed that solves the lockmaster's problem in polynomial time. We extend this DP to different generalizations that consider weights, water usage, capacity, and (a fixed number of) multiple chambers. Finally, we prove that the problem becomes strongly NP-hard when the number of chambers is part of the input.
Cite as

Sofie Coene and Frits C. R. Spieksma. The Lockmaster's problem. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 27-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{coene_et_al:OASIcs.ATMOS.2011.27,
  author =	{Coene, Sofie and Spieksma, Frits C. R.},
  title =	{{The Lockmaster's problem}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{27--37},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.27},
  URN =		{urn:nbn:de:0030-drops-32647},
  doi =		{10.4230/OASIcs.ATMOS.2011.27},
  annote =	{Keywords: lock scheduling, batch scheduling, dynamic programming, complexity}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.34
Heuristics for the Traveling Repairman Problem with Profits

Authors: Thijs Dewilde, Dirk Cattrysse, Sofie Coene, Frits C. R. Spieksma, and Pieter Vansteenwegen

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
In the traveling repairman problem with profits, a repairman (also known as the server) visits a subset of nodes in order to collect time-dependent profits. The objective consists of maximizing the total collected revenue. We restrict our study to the case of a single server with nodes located in the Euclidean plane. We investigate properties of this problem, and we derive a mathematical model assuming that the number of visited nodes is known in advance. We describe a tabu search algorithm with multiple neighborhoods, and we test its performance by running it on instances based on TSPLIB. We conclude that the tabu search algorithm finds good-quality solutions fast, even for large instances.
Cite as

Thijs Dewilde, Dirk Cattrysse, Sofie Coene, Frits C. R. Spieksma, and Pieter Vansteenwegen. Heuristics for the Traveling Repairman Problem with Profits. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 34-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dewilde_et_al:OASIcs.ATMOS.2010.34,
  author =	{Dewilde, Thijs and Cattrysse, Dirk and Coene, Sofie and Spieksma, Frits C. R. and Vansteenwegen, Pieter},
  title =	{{Heuristics for the Traveling Repairman Problem with Profits}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{34--44},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.34},
  URN =		{urn:nbn:de:0030-drops-27489},
  doi =		{10.4230/OASIcs.ATMOS.2010.34},
  annote =	{Keywords: Traveling Repairman, Profits, Latency, Tabu Search, Relief Efforts}
}

Spieksma, Frits C.R.

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.49
Package Delivery Using Drones with Restricted Movement Areas

Authors: Thomas Erlebach, Kelin Luo, and Frits C.R. Spieksma

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
For the problem of delivering a package from a source node to a destination node in a graph using a set of drones, we study the setting where the movements of each drone are restricted to a certain subgraph of the given graph. We consider the objectives of minimizing the delivery time (problem DDT) and of minimizing the total energy consumption (problem DDC). For general graphs, we show a strong inapproximability result and a matching approximation algorithm for DDT as well as NP-hardness and a 2-approximation algorithm for DDC. For the special case of a path, we show that DDT is NP-hard if the drones have different speeds. For trees, we give optimal algorithms under the assumption that all drones have the same speed or the same energy consumption rate. The results for trees extend to arbitrary graphs if the subgraph of each drone is isometric.
Cite as

Thomas Erlebach, Kelin Luo, and Frits C.R. Spieksma. Package Delivery Using Drones with Restricted Movement Areas. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.ISAAC.2022.49,
  author =	{Erlebach, Thomas and Luo, Kelin and Spieksma, Frits C.R.},
  title =	{{Package Delivery Using Drones with Restricted Movement Areas}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.49},
  URN =		{urn:nbn:de:0030-drops-173343},
  doi =		{10.4230/LIPIcs.ISAAC.2022.49},
  annote =	{Keywords: Mobile agents, approximation algorithm, inapproximability}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.92
Mathematical programming models for scheduling locks in sequence

Authors: Ward Passchyn, Dirk Briskorn, and Frits C.R. Spieksma

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
We investigate the scheduling of series of consecutive locks. This setting occurs naturally along canals and waterways. We describe a problem that generalizes different models that have been studied in literature. Our contribution is to (i) provide two distinct mathematical programming formulations, and compare them empirically, (ii) show how these models allow for minimizing emission by having the speed of a ship as a decision variable, (iii) to compare, on realistic instances, the optimum solution found by solving the models with the outcome of a decentralized heuristic.
Cite as

Ward Passchyn, Dirk Briskorn, and Frits C.R. Spieksma. Mathematical programming models for scheduling locks in sequence. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 92-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{passchyn_et_al:OASIcs.ATMOS.2014.92,
  author =	{Passchyn, Ward and Briskorn, Dirk and Spieksma, Frits C.R.},
  title =	{{Mathematical programming models for scheduling locks in sequence}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{92--106},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.92},
  URN =		{urn:nbn:de:0030-drops-47553},
  doi =		{10.4230/OASIcs.ATMOS.2014.92},
  annote =	{Keywords: Mixed Integer Programming, Inland Waterways, Lock Scheduling}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact